package LeetCode;

import java.util.HashMap;
import java.util.HashSet;

/**
 * Created by kechelle on 2020/8/22 20:51
 * 只出现一次的数字II,区别于136题，有的数字出现三次或者奇数次
 */
public class Code137 {
    //借助HashMap
    public static int singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num:nums){
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }
        for (Integer key:map.keySet()){
            if (map.get(key)==1) return key;
        }
        return -1;
    }

    //借助数学算法,但存在结果溢出,不推荐
    public static int singleNumber1(int[] nums){
        int sum = 0,sumSet = 0;
        HashSet<Integer> set = new HashSet();
        for (int num:nums){
            sum+=num;
            set.add(num);
        }
        for (int num:set){
            sumSet+=num;
        }
        sumSet = sumSet * 3;
        return (sumSet - sum)/2;
    }

    //二进制算法
    public static int singleNumber2(int[] nums){
        int res = 0;
        for (int i=0;i<32;i++){

            int sum = 0;
            for (int j=0;j<nums.length;j++){
                //查看当前位是否是1，并计算当前位1的个数
                sum += (nums[j]>>i) & 1;
            }
            //如果每一列1的总数是3的倍数，把是3倍数的列都写0，不是3倍数的列写1
            res ^= (sum%3)<<i;
        }
        return res;
    }

    //位运算符,用时较快，来自国外题解
    public static int singleNumber3(int[] nums){
        int one = 0,two = 0;
        for (int num:nums){
            one = ~two & (one ^ num);
            two = ~one & (two ^ num);
        }
        return one;
    }

    public static void main(String[] args) {
        int[] nums = {3,3,2,3};
        System.out.println(Code137.singleNumber2(nums));
    }
}
